Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Знаходження шляхів графа

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики

Інформація про роботу

Рік:
2009
Тип роботи:
Лабораторна робота
Предмет:
Математика
Група:
ПМ-21

Частина тексту файла

Міністерство освіти та науки України Національний університет «Львівська політехніка» Інститут прикладної математики та фундаментальних наук Кафедра прикладної математики Лабораторна робота №2 «Знаходження шляхів графа» Тема: знаходження шляхів в графі. Мета: дати можливість студентам детальніше в практичному відношенні засвоїти тему по знаходженню різних шляхів в графах за допомогою засобів ЕОМ. Теоретичні відомості: В практиці дуже часто приходиться мати справу з задачами знаходження шляхів і контурів певних графів. Цю задачу доцільно розділити на два типи, а саме: 1) кількісна оцінка шляхів графа; 2) якісна оцінка шляхів графа (деякі екстремальні задачі на графах). Саме до першого типу відноситься задача знаходження шляхів, що відповідають трійці цілих невід’ємних чисел α, β, γ. Якщо в графі G(x) через  позначити число дуг, що йдуть з вершини  в вершину , то матриця  з n-стрічками і n-стовпцями називаэться матрицею суміжності вершин графа G(x). Число шляхів, які відповідають даній трійці невід’ємних цілих чисел. Говорять, що шлях  відповідає трійці α, β, γ чисел, якщо на цьому шляху є дві однакові вершини  та ,  для яких . Тут  – означає довжину шляху M між точками . Якщо A – матриця суміжності графа G, а  – число шляхів, які відповідають трійці чисел α, β, γ і які йдуть від  до , то  де  – означає матрицю, головна діагональ якої така ж, що й в , а всі інші елементи – нулі. Завдання: знайти число шляхів, які відповідають деякій трійці невід’ємних чисел α, β, γ для матриці суміжності . Код програми(С++): #include <iostream> #define m 6 using namespace std; void Out_Matrix(int A[m][m], int n); void Null_Matrix(int A[m][m]); void Multiply_Matrix(int A[m][m], int B[m][m], int C[m][m void Pow_Matrix(int A[m][m], int As[m][m], int s void D_Matrix(int A[m][m], int B[m][m void Make_Matrix(int A[m][m], int B[m][m], int a, int b, int c); int M[m][m] = {1,1,0,1,1,1, 0,0,1,1,1,0, 1,0,1,0,0,0, 1,0,0,1,1,0, 1,1,0,0,1,1, 0,1,0,1,0,1}; void main() { cout<<"Znahodzhennja 4usla shljahiv, jaki vidpovidajyt' dejakij trijci"<<endl <<"nevidjemnuh 4usel a, b, c dlja matruci symizhnosti:"; Out_Matrix(M, m); int a, b, c, R[m][m]; cout<<"Vvedit' 4usla a, b, c:"; go: cin>>a>>b>>c; if ((a < 0)||(b < 0)||(c < 0)) {cout<<"4usla povuni bytu nevidjemni!"; goto go;}; Make_Matrix(M, R, a, b ,c); Out_Matrix(R, m); } //Îïèñ ôóíêö³é void Out_Matrix(int A[m][m], int n) { for(int i = 0; i < n; i++) { cout<<endl; for(int j = 0; j < n; j++) cout<<A[i][j]<<" "; } cout<<endl; } void Null_Matrix(int A[m][m]) { for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) { A[i][j] = 0; } } void Multiply_Matrix(int A[m][m], int B[m][m], int C[m][m]) { for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) { C[i][j] = 0; for(int k = 0; k < m; k++) C[i][j] += (A[i][k] * B[k][j]); } } void Pow_Matrix(int A[m][m], int As[m][m], int s) { int R[m][m]; for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) if (i == j) As[i][j] = 1; else As[i][j] = 0; if (s != 0) for(int k = 0; k < s; k++) { Multiply_Matrix(A, As, R); for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) As[i][j] = R[i][j]; } } void D_Matrix(int A[m][m], int B[m][m]) { for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) if (i!=j) B[i][j] = 0; else B[i][j] = A[i][j]; } void Make_Matrix(int A[m][m], int B[m][m], int a, int b, int c) { int R1[m][m], R2[m][m], dR2[m][m], R3[m][m]; Pow_Matrix(A, R1, a); Pow_Matrix(A, R2, b); Pow_Matrix(A, R3, c); D_Matrix(R2, dR2); Multiply_Matrix(R1, dR2, R2); Multiply_Matrix(R2, R3, B); } Результати програми: Znahodzhennja 4usla shljahiv, jaki vidpovidajyt' dejakij trijci nevidjemnuh 4usel a, b, c dlja matruci symizhnosti: 1 1 0 1 1 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 Vvedit' 4usla a, b, c: 0 1 2 3 3 1 4 4 3 0 0 0 0 0 0 2 1 1 1 1 1 3 2 0 2 3 2 2 3...
Антиботан аватар за замовчуванням

01.01.1970 03:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини